package leetcode_en

import (
	"go-study/src/leetcode"
	"go-study/src/utils"
	"math"
	"sort"
	"strconv"
	"strings"
)

/**
 * @Description: 219. Contains Duplicate II
 * @Keyword: 类似TwoSum
 * @Author: kami
 * @Date: 2021/12/10 23:44
 **/
func containsNearbyDuplicate(nums []int, k int) bool {
	seen := make(map[int]int)
	size := len(nums)
	for i := 0; i < size; i++ {
		if i > k {
			delete(seen, nums[i-k-1])
		}
		if _, ok := seen[nums[i]]; ok {
			return true
		}
		seen[nums[i]] = 0
	}
	return false
}

/**
 * @Description: 225. Implement Stack using Queues
 * @Keyword: 先实现队列，再用队列实现栈
 * @Author: kami
 * @Date: 2021/12/11 11:34
 **/
type MyStack struct {
	head *DoubleDirectionListNode
	tail *DoubleDirectionListNode
	size int
}
type DoubleDirectionListNode struct {
	Val  int
	Next *DoubleDirectionListNode
	Pre  *DoubleDirectionListNode
}

func Constructor() MyStack {
	return MyStack{}
}

func (this *MyStack) Push(x int) {
	if this.head == nil {
		node := &DoubleDirectionListNode{Val: x}
		this.head = node
		this.tail = node
	}
	newTail := &DoubleDirectionListNode{Val: x}
	this.tail.Next = newTail
	newTail.Pre = this.tail
	this.tail = newTail
	this.size++
}

func (this *MyStack) Pop() int {
	val := this.tail.Val
	this.tail = this.tail.Pre
	this.tail.Next = nil
	this.size--
	return val
}

func (this *MyStack) Top() int {
	return this.tail.Val
}

func (this *MyStack) Empty() bool {
	return this.size == 0
}

/**
 * @Description: 228. Summary Ranges
 * @Keyword: 细粒度的有序数组
 * @Author: kami
 * @Date: 2021/12/12 22:29
 **/
func summaryRanges(nums []int) []string {
	size := len(nums)
	res := make([]string, 0)
	for i := 0; i < size; i++ {
		curVal := nums[i]
		for i+1 < size && nums[i+1]-nums[i] == 1 {
			i++
		}
		if curVal != nums[i] {
			res = append(res, strconv.Itoa(curVal)+"->"+strconv.Itoa(nums[i]))
		} else {
			res = append(res, strconv.Itoa(curVal))
		}
	}
	return res
}

/**
 * @Description: 231. Power of Two
 * @Keyword: 2的幂
 * @Author: kami
 * @Date: 2021/12/12 22:59
 **/
func isPowerOfTwo(n int) bool {
	return n != 0 && n&(n-1) == 0
}

/**
 * @Description: 235. Lowest Common Ancestor of a Binary Search Tree
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2021/12/13 22:25
 **/
func lowestCommonAncestor(root, p, q *leetcode.TreeNode) *leetcode.TreeNode {
	var pNode = &Node{
		CurNode: p,
	}
	var qNode = &Node{
		CurNode: q,
	}
	dfsNode(root, nil, pNode, qNode)
	var pMap = make(map[*Node]bool)
	for pNode != nil {
		pMap[pNode] = true
		pNode = pNode.Parent
	}
	for qNode != nil {
		if pMap[qNode] {
			return qNode.CurNode
		}
		qNode = qNode.Parent
	}

	return nil
}

type Node struct {
	CurNode *leetcode.TreeNode
	Parent  *Node
}

func dfsNode(root *leetcode.TreeNode, parent *Node, p *Node, q *Node) {
	var curNode *Node
	switch root {
	case nil:
		return
	case p.CurNode:
		p.Parent = parent
		curNode = p
	case q.CurNode:
		q.Parent = parent
		curNode = q
	default:
		curNode = &Node{
			CurNode: root,
			Parent:  parent,
		}
	}
	dfsNode(root.Left, curNode, p, q)
	dfsNode(root.Right, curNode, p, q)
}

/**
 * @Description: 257. Binary Tree Paths
 * @Keyword: 递归遍历
 * @Author: kami
 * @Date: 2021/12/14 23:01
 **/
func binaryTreePaths(root *leetcode.TreeNode) []string {
	var curStr = strconv.Itoa(root.Val)
	if root.Left == nil && root.Right == nil {
		return []string{curStr}
	}
	var list []string
	if root.Left != nil {
		list = dfsPath(root.Left, curStr, []string{})
	}
	if root.Right != nil {
		list = dfsPath(root.Right, curStr, list)

	}
	return list
}

func dfsPath(cur *leetcode.TreeNode, curStr string, list []string) []string {
	if cur.Left == nil && cur.Right == nil {
		curStr += "->" + strconv.Itoa(cur.Val)
		list = append(list, curStr)
		return list
	}
	var curStr1 = curStr + "->" + strconv.Itoa(cur.Val)
	if cur.Left != nil {
		list = dfsPath(cur.Left, curStr1, list)
	}
	if cur.Right != nil {
		list = dfsPath(cur.Right, curStr1, list)
	}
	return list
}

/**
 * @Description: 258. Add Digits
 * @Keyword: 数字转字符串，字符串转数字
 * @Author: kami
 * @Date: 2021/12/15 21:17
 **/
func addDigits(num int) int {
	if num < 10 {
		return num
	}
	var numStr = strconv.Itoa(num)
	for len(numStr) >= 2 {
		var cnt = 0
		for i := 0; i < len(numStr); i++ {
			cnt += int(numStr[i] - '0')
		}
		numStr = strconv.Itoa(cnt)
	}

	i, _ := strconv.ParseInt(numStr, 10, 0)
	return int(i)
}

/**
 * @Description: 263. Ugly Number
 * @Keyword: 质因数
 * @Author: kami
 * @Date: 2021/12/15 21:36
 **/
func isUgly(n int) bool {
	for i := 2; i <= 6 && n > 0; i++ {
		for n%i == 0 {
			n /= i
		}
	}
	return n == 1
}

/**
 * @Description: 278. First Bad Version
 * @Keyword: 找到最开始的bug版本，二分查找
 * @Author: kami
 * @Date: 2021/12/15 22:13
 **/
func firstBadVersion(n int) int {
	var left, mid, right = 1, n / 2, n
	if isBadVersion(1) {
		return 1
	}
	for {
		if isBadVersion(mid) {
			if !isBadVersion(mid - 1) {
				return mid
			}
			right = mid
		} else {
			if isBadVersion(mid + 1) {
				return mid + 1
			}
			left = mid
		}
		mid = (left + right) / 2
	}
}

func isBadVersion(version int) bool {
	return false
}

/**
 * @Description: 290. Word Pattern
 * @Keyword: map记录出现位置
 * @Author: kami
 * @Date: 2021/12/15 22:33
 **/
func wordPattern(pattern string, s string) bool {
	size := len(pattern)
	ss := strings.Split(s, " ")
	if len(ss) != size {
		return false
	}
	seenPatternMap := make(map[byte]int)
	seenStrMap := make(map[string]int)
	for i := 0; i < size; i++ {
		idx, ok := seenPatternMap[pattern[i]]
		idx2, ok2 := seenStrMap[ss[i]]
		switch {
		case ok && !ok2:
			return false
		case !ok && ok2:
			return false
		case ok && ok2 && idx != idx2:
			return false
		default:
			seenPatternMap[pattern[i]] = i
			seenStrMap[ss[i]] = i
		}
	}
	return true

}

/**
 * @Description: 292. Nim Game
 * @Keyword: 当我之前没说
 * @Author: kami
 * @Date: 2021/12/16 23:03
 **/
func canWinNim(n int) bool {
	return n%4 != 0
}

/**
 * @Description: 342. Power of Four
 * @Keyword: 取余数
 * @Author: kami
 * @Date: 2021/12/18 10:34
 **/
func isPowerOfFour(n int) bool {
	if n == 1 {
		return true
	}
	// 不是2的幂次方，更不会是4的幂次方
	if n&(n-1) != 0 {
		return false
	}
	for n != 1 {
		if n%4 != 0 {
			return false
		}
		n >>= 2
	}
	return true
}

/**
 * @Description: 345. Reverse Vowels of a String
 * @Keyword: 今年上半年微软面试中遇到过 https://github.com/onedayguo/start-up-one/blob/master/start-up/src/main/java/interview/MS.java
 * @Author: kami
 * @Date: 2021/12/18 10:50
 **/
func reverseVowels(s string) string {
	size := len(s)
	var left, right = 0, size - 1
	vowelMap := map[byte]bool{
		'a': true,
		'e': true,
		'i': true,
		'o': true,
		'u': true,
		'A': true,
		'E': true,
		'I': true,
		'O': true,
		'U': true,
	}
	sByte := []byte(s)
	for left < right {
		for left < right && left < size && !vowelMap[sByte[left]] {
			left++
		}
		for left < right && right > 0 && !vowelMap[sByte[right]] {
			right--
		}
		if left < right {
			temp := sByte[right]
			sByte[right] = sByte[left]
			sByte[left] = temp
			left++
			right--
		}
	}
	return string(sByte)
}

/**
 * @Description: 349. Intersection of Two Arrays
 * @Keyword: 利用数组下标存值表示是否存在，但是只适用于数据量较少的情况下，因为要开辟长度味n的数组
 * @Author: kami
 * @Date: 2021/12/18 11:35
 **/
func intersection(nums1 []int, nums2 []int) []int {
	size1 := len(nums1)
	size2 := len(nums2)

	var intArr = new([1001]int)
	for i := 0; i < size1; i++ {
		intArr[nums1[i]] += 1
	}

	var res []int
	for i := 0; i < size2; i++ {
		if intArr[nums2[i]] > 0 {
			res = append(res, nums2[i])
		}
	}

	return res
}

/**
 * @Description: 367. Valid Perfect Square
 * @Keyword: 数字是否是N的平方;想起一个算法“牛顿迭代”，二分查找
 * @Author: kami
 * @Date: 2021/12/18 12:00
 **/
func isPerfectSquare(num int) bool {
	if num == 1 || num == 2 {
		return true
	}
	for i := 2; i <= num/2; i++ {
		squre := i * i
		if squre > num {
			return false
		} else if squre == num {
			return true
		}
	}
	return false
}

/**
 * @Description: 374. Guess Number Higher or Lower
 * @Keyword: 有序数组，二分查找
 * @Author: kami
 * @Date: 2021/12/18 18:04
 **/
func guessNumber(n int) int {
	if guess(n) == 0 {
		return n
	}
	var low, mid, high = 1, n / 2, n
	for low < high {
		switch guess(mid) {
		case 0:
			return mid
		case 1:
			low = mid
		case -1:
			high = mid
		}
		mid = (low + high) / 2
	}
	return mid
}

func guess(num int) int {
	if num < 6 {
		return 1
	} else if num > 6 {
		return -1
	}
	return 0
}

/**
 * @Description: 383. Ransom Note
 * @Keyword: ransomNote字符是否全部出现在magazine中;利用数组下标
 * @Author: kami
 * @Date: 2021/12/18 18:26
 **/
func canConstruct(ransomNote string, magazine string) bool {
	// 26长度
	var exist = new([26]int)
	for i := 0; i < len(magazine); i++ {
		exist[magazine[i]-'a'] += 1
	}
	for i := 0; i < len(ransomNote); i++ {
		if exist[ransomNote[i]-'a'] <= 0 {
			return false
		}
		exist[ransomNote[i]-'a'] -= 1
	}
	return true
}

/**
 * @Description: 389. Find the Difference
 * 这道题的描述不严谨，没有说明s中多出的是否能出现在t中的，但是不影响深层次的理解
 * @Keyword: 利用数组下标这招真好使,这跟上面383简直一模一样了
 * @Author: kami
 * @Date: 2021/12/18 18:34
 **/
func findTheDifference(s string, t string) byte {
	// 1.存t中的字符
	var exist = new([26]int)
	for i := 0; i < len(s); i++ {
		exist[s[i]-'a'] += 1
	}

	// 遍历s
	for i := 0; i < len(t); i++ {
		if exist[t[i]-'a'] <= 0 {
			return t[i]
		}
		exist[t[i]-'a'] -= 1
	}
	return t[0]
}

/**
 * @Description: 404. Sum of Left Leaves
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2021/12/18 18:59
 **/
func sumOfLeftLeaves(root *leetcode.TreeNode) int {
	return dfsLeft(root, false)
}

func dfsLeft(cur *leetcode.TreeNode, isLeftNode bool) int {
	if cur.Left == nil && cur.Right == nil {
		if isLeftNode {
			return cur.Val
		}
		return 0
	}
	var sum = 0
	if cur.Left != nil {
		sum += dfsLeft(cur.Left, true)
	}
	if cur.Right != nil {
		sum += dfsLeft(cur.Right, false)
	}
	return sum
}

/**
 * @Description: 405. Convert a Number to Hexadecimal
 * @Keyword: 进制转换
 * @Author: kami
 * @Date: 2021/12/18 19:16
 **/
func toHex(num int) string {

	if num == 0 {
		return "0"
	}

	if num < 0 {
		num = -num
		num ^= 0xffffffff
		num += 1
	}

	res := ""
	arr := []byte{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'}
	for num > 0 {
		digit := num % 16
		res = string(arr[digit]) + res
		num /= 16
	}
	return res
}

/**
 * @Description: 409. Longest Palindrome
 * @Keyword: 租场回文字符串
 * @Author: kami
 * @Date: 2021/12/18 19:36
 **/
func longestPalindrome(s string) int {
	// A-Z 6个其他字符，a-z 一共58个字符
	var exist = new([58]int)
	for i := 0; i < len(s); i++ {
		exist[s[i]-65] += 1
	}
	var cnt int
	var hasSingle bool
	for i := 0; i < 58; i++ {
		if !hasSingle && exist[i]%2 == 1 {
			hasSingle = true
		}
		cnt += exist[i] / 2
	}
	if hasSingle {
		return 2*cnt + 1
	}
	return 2 * cnt
}

/**
 * @Description: 414. Third Maximum Number
 * @Keyword: 维护三个最大值
 * @Author: kami
 * @Date: 2021/12/18 20:16
 **/
func thirdMax(nums []int) int {
	var max, second, third = ^int(^uint(0) >> 1), ^int(^uint(0) >> 1), ^int(^uint(0) >> 1)
	for i := 0; i < len(nums); i++ {
		if nums[i] > max {
			third = second
			second = max
			max = nums[i]
		} else if nums[i] == max {
			continue
		} else if nums[i] > second {
			third = second
			second = nums[i]
		} else if nums[i] == second {
			continue
		} else if nums[i] > third {
			third = nums[i]
		}
	}
	if max != second && second != third && third != ^int(^uint(0)>>1) {
		return third
	}
	return max
}

/**
 * @Description: 434. Number of Segments in a String
 * @Keyword: 找模式，如果不符合模式，则补全数据使其符合模式
 * @Author: kami
 * @Date: 2021/12/18 20:49
 **/
func countSegments(s string) int {
	var cnt int
	s = " " + s
	for i := 1; i < len(s); i++ {
		if s[i-1] == ' ' && s[i] != ' ' {
			cnt++
		}
	}
	return cnt

}

/**
 * @Description: 441. Arranging Coins
 * @Keyword: 累加
 * @Author: kami
 * @Date: 2021/12/18 20:58
 **/
func arrangeCoins(n int) int {
	var cnt int
	for i := 1; i <= n; i++ {
		temp := cnt + i
		if cnt+i < n {
			cnt = temp
		} else {
			return i - 1
		}
	}
	return n
}

/**
 * @Description: 455. Assign Cookies
 * @Keyword: 先排序，后统计
 * @Author: kami
 * @Date: 2021/12/19 8:33
 **/
func findContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	var cookieIdx int
	var cookieSize = len(s)
	var cnt int
	for i := 0; i < len(g); i++ {
		for cookieIdx < cookieSize && s[cookieIdx] < g[i] {
			cookieIdx++
		}
		if cookieIdx >= cookieSize {
			return cnt
		}
		cnt++
		cookieIdx++
	}
	return cnt
}

/**
 * @Description: 459. Repeated Substring Pattern
 * @Keyword: 构造重复
 * @Author: kami
 * @Date: 2021/12/19 8:53
 **/
func repeatedSubstringPattern(s string) bool {
	if len(s) == 0 {
		return false
	}

	size := len(s)
	ss := (s + s)[1 : size*2-1]

	return strings.Contains(ss, s)
}

/**
 * @Description: 461. Hamming Distance
 * @Keyword: 进制转换，移位操作
 * @Author: kami
 * @Date: 2021/12/19 9:53
 **/
func hammingDistance(x int, y int) int {
	m := x ^ y
	var cnt int
	for i := 31; i >= 0; i-- {
		move := m >> i
		if move == 1 {
			cnt += 1
			m -= 1 << i
		}
	}
	return cnt
}

/**
 * @Description: 463. Island Perimeter
 * @Keyword: 找规律
 * @Author: kami
 * @Date: 2021/12/19 10:49
 **/
func islandPerimeter(grid [][]int) int {
	var isLads, neighbours int
	width := len(grid[0])
	height := len(grid)
	for i := 0; i < height; i++ {
		for j := 0; j < width; j++ {
			if grid[i][j] == 1 {
				isLads++
				if i < height-1 && grid[i+1][j] == 1 {
					neighbours++
				}
				if j < width-1 && grid[i][j+1] == 1 {
					neighbours++
				}
			}

		}
	}
	return isLads*4 - neighbours*2
}

/**
 * @Description: 476. Number Complement
 * @Keyword: 实现取反运算
 * @Author: kami
 * @Date: 2021/12/19 11:24
 **/
func findComplement(num int) int {
	var cnt int
	var start bool
	for i := 31; i >= 0; i-- {
		move := num >> i
		if !start && move == 1 {
			start = true
		}
		if start {
			if move == 1 {
				num -= 1 << i
			} else {
				cnt += 1 << i
			}
		}
	}
	return cnt
}

/**
 * @Description: 482. License Key Formatting
 * @Keyword: 去除划线，小写变大写，k个一组，从后向前
 * @Author: kami
 * @Date: 2021/12/19 12:27
 **/
func licenseKeyFormatting(s string, k int) string {
	size := len(s)
	resByte := make([]byte, 0)
	var cnt int
	for i := size - 1; i >= 0; i-- {
		if s[i] != '-' {
			var big = s[i]
			if s[i] >= 'a' && s[i] <= 'z' {
				big -= 32
			}
			if cnt+1 == k {
				resByte = append([]byte{'-', big}, resByte...)
				cnt = 0
			} else {
				resByte = append([]byte{big}, resByte...)
				cnt++
			}
		}
	}
	if len(resByte) > 0 && resByte[0] == '-' {
		return string(resByte[1:])
	}
	return string(resByte)
}

/**
 * @Description: 485. Max Consecutive Ones
 * @Keyword: 连续数1
 * @Author: kami
 * @Date: 2021/12/20 21:26
 **/
func findMaxConsecutiveOnes(nums []int) int {
	var max int
	var curCnt int
	for i := 0; i < len(nums); i++ {
		if nums[i] == 1 {
			curCnt += 1
			if curCnt > max {
				max = curCnt
			}
		} else {
			curCnt = 0
		}
	}
	return max
}

/**
 * @Description: 492. Construct the Rectangle
 * @Keyword: 找n的平方等于目标值
 * @Author: kami
 * @Date: 2021/12/20 21:29
 **/
func constructRectangle(area int) []int {
	num := int(math.Sqrt(float64(area)))
	for area%num != 0 {
		num--
	}
	var num2 = area / num
	if num2 > num {
		return []int{num2, num}
	}
	return []int{num, num2}
}

/**
 * @Description: 495. Teemo Attacking
 * @Keyword: 差值
 * @Author: kami
 * @Date: 2021/12/20 22:06
 **/
func findPoisonedDuration(timeSeries []int, duration int) int {
	if duration == 0 {
		return 0
	}
	size := len(timeSeries)
	if size == 1 {
		return duration
	}
	var cnt int
	for i := 1; i < len(timeSeries); i++ {
		diff := timeSeries[i] - timeSeries[i-1]
		if diff >= duration {
			cnt += duration
		} else {
			cnt += diff
		}
	}
	return cnt + duration
}

/**
 * @Description: 496. Next Greater Element I
 * @Keyword: 插入排序
 * @Author: kami
 * @Date: 2021/12/21 23:06
 **/
func nextGreaterElement(nums1 []int, nums2 []int) []int {
	nearMap := make(map[int]int)
	var sortNum2 []int
	for i := 0; i < len(nums2); i++ {
		var sortIdx int
		var size = len(sortNum2)
		for sortIdx < size && nums2[i] > sortNum2[sortIdx] {
			nearMap[sortNum2[sortIdx]] = nums2[i]
			sortIdx++
		}
		if sortIdx < size {
			sortNum2 = sortNum2[sortIdx:]
		} else {
			sortNum2 = []int{}
		}
		size = len(sortNum2)
		if size <= 0 {
			sortNum2 = append(sortNum2, nums2[i])
			continue
		}

		var insertIdx int
		for j := 0; j < size; j++ {
			if nums2[i] > sortNum2[j] {
				insertIdx++
			} else {
				break
			}
		}
		if insertIdx >= size {
			sortNum2 = append(sortNum2, nums2[i])
		} else if insertIdx == 0 {
			sortNum2 = append([]int{nums2[i]}, sortNum2...)
		} else {
			secondPart := sortNum2[insertIdx:]
			sortNum2 = append(sortNum2[0:insertIdx], nums2[i])
			sortNum2 = append(sortNum2, secondPart...)
		}
	}
	var res []int
	for i := 0; i < len(nums1); i++ {
		if val, ok := nearMap[nums1[i]]; ok {
			res = append(res, val)
		} else {
			res = append(res, -1)
		}
	}
	return res
}

/**
 * @Description: 500. Keyboard Row
 * @Keyword: map
 * @Author: kami
 * @Date: 2021/12/22 21:57
 **/
func findWords(words []string) []string {
	first := map[byte]bool{
		'q': true,
		'w': true,
		'e': true,
		'r': true,
		't': true,
		'y': true,
		'u': true,
		'i': true,
		'o': true,
		'p': true,
	}
	second := map[byte]bool{
		'a': true,
		's': true,
		'd': true,
		'f': true,
		'g': true,
		'h': true,
		'j': true,
		'k': true,
		'l': true,
	}
	third := map[byte]bool{
		'z': true,
		'x': true,
		'c': true,
		'v': true,
		'b': true,
		'n': true,
		'm': true,
	}
	var res []string
	for i := 0; i < len(words); i++ {
		var rightMap map[byte]bool
		if first[words[i][0]] || first[words[i][0]+32] {
			rightMap = first
		} else if second[words[i][0]] || second[words[i][0]+32] {
			rightMap = second
		} else {
			rightMap = third
		}
		var idx = 1
		var size = len(words[i])
		for j := 1; j < size; j++ {
			if !rightMap[words[i][j]] && !rightMap[words[i][j]+32] {
				idx -= 1
				break
			}
			idx = j
		}
		if idx >= size-1 {
			res = append(res, words[i])
		}
	}
	return res
}

/**
 * @Description: 501. Find Mode in Binary Search Tree
 * @Keyword: 递归遍历
 * @Author: kami
 * @Date: 2021/12/22 22:32
 **/
func findMode(root *leetcode.TreeNode) []int {
	var max = []int{root.Val}
	if root.Left == nil && root.Right == nil {
		return max
	}
	seenMap := make(map[int]int)
	dfsMode(root, seenMap)
	for val, cnt := range seenMap {
		if cnt > seenMap[max[0]] && val != max[0] {
			max = []int{val}
		} else if cnt == seenMap[max[0]] && val != max[0] {
			max = append(max, val)
		}
	}
	return max
}

func dfsMode(curNode *leetcode.TreeNode, seenMap map[int]int) {
	if curNode == nil {
		return
	}
	seenMap[curNode.Val] += 1
	dfsMode(curNode.Left, seenMap)
	dfsMode(curNode.Right, seenMap)
}

/**
 * @Description: 504. Base 7
 * @Keyword: 进制转换
 * @Author: kami
 * @Date: 2021/12/22 23:06
 **/
func convertToBase7(num int) string {
	if num < 0 {
		return "-" + convertToBase7(-num)
	}
	if num < 7 {
		return strconv.Itoa(num)
	}
	return convertToBase7(num/7) + strconv.Itoa(num%7)
}

/**
 * @Description: 506. Relative Ranks
 * @Keyword: 10, 3, 8, 9, 4
 * @Author: kami
 * @Date: 2021/12/23 22:09
 **/
func findRelativeRanks(score []int) []string {
	size := len(score)
	idxMap := make(map[int]int)

	var sortScore = make([]int, size)
	for i := 0; i < size; i++ {
		sortScore[i] = score[i]
	}
	sort.Ints(sortScore)
	for i := size - 1; i >= 0; i-- {
		idxMap[sortScore[i]] = size - i
	}
	var res []string
	for i := 0; i < size; i++ {
		th := idxMap[score[i]]
		switch th {
		case 1:
			res = append(res, "Gold Medal")
		case 2:
			res = append(res, "Silver Medal")
		case 3:
			res = append(res, "Bronze Medal")
		default:
			res = append(res, strconv.Itoa(th))
		}
	}
	return res
}

/**
 * @Description: 507. Perfect Number
 * @Keyword: 平方根
 * @Author: kami
 * @Date: 2021/12/24 9:20
 **/
func checkPerfectNumber(num int) bool {
	if num == 1 {
		return false
	}
	var sum int
	for i := 2; i <= int(math.Sqrt(float64(num))); i++ {
		if num%i == 0 {
			sum += i + num/i
		}
	}
	sum++

	return sum == num
}

/**
 * @Description: 520. Detect Capital
 * @Keyword: 是否是大写单词
 * @Author: kami
 * @Date: 2021/12/24 20:54
 **/
func detectCapitalUse(word string) bool {
	size := len(word)
	if size == 1 {
		return true
	}
	if size >= 2 {
		// 第一位小写，第二位大写
		if word[0] >= 97 && word[1] < 97 {
			return false
		}
	}
	fn := getCompareFunc(word[1])
	for i := 2; i < len(word); i++ {
		if !fn(word[i]) {
			return false
		}
	}
	return true
}

func getCompareFunc(b byte) func(b byte) bool {
	if b < 97 {
		return func(b byte) bool {
			return b < 97
		}
	}
	return func(b byte) bool {
		return b >= 97
	}
}

/**
 * @Description: 521. Longest Uncommon Subsequence I
 * @Keyword: 最长非同质字符串长度;有问题的题
 * @Author: kami
 * @Date: 2021/12/24 21:12
 **/
func findLUSlength(a string, b string) int {
	if a == b {
		return -1
	}
	if len(a) > len(b) {
		return len(a)
	}
	return len(b)
}

/**
 * @Description: 530. Minimum Absolute Difference in BST
 * @Keyword: 非平衡二叉树
 * @Author: kami
 * @Date: 2021/12/25 10:52
 **/
func getMinimumDifference(root *leetcode.TreeNode) int {
	_, _, diff := helper(root)
	return diff
}

func helper(node *leetcode.TreeNode) (int, int, int) {
	min, max, diff := node.Val, node.Val, math.MaxInt32
	if node.Left != nil {
		lMin, lMax, lDiff := helper(node.Left)
		min = lMin
		if tempDiff := node.Val - lMax; tempDiff < diff {
			diff = tempDiff
		}
		if lDiff < diff {
			diff = lDiff
		}
	}
	if node.Right != nil {
		rMin, rMax, rDiff := helper(node.Right)
		max = rMax
		if tempDiff := rMin - node.Val; tempDiff < diff {
			diff = tempDiff
		}
		if rDiff < diff {
			diff = rDiff
		}
	}
	return min, max, diff
}

/**
 * @Description: 541. Reverse String II
 * @Keyword: 交换
 * @Author: kami
 * @Date: 2021/12/26 21:46
 **/
func reverseStr(s string, k int) string {
	sBytes := []byte(s)
	size := len(s)
	var i int
	for i < size {
		var j = utils.GetMin(i+k-1, size-1)
		utils.SwapBetween(sBytes, i, j)
		i += 2 * k
	}
	return string(sBytes)
}

/**
 * @Description: 551. Student Attendance Record I
 * @Keyword: 是否不合格，检查是否满足条件
 * @Author: kami
 * @Date: 2021/12/27 21:47
 **/
func checkRecord(s string) bool {
	size := len(s)
	var aCnt int
	var lCog3 int
	var pre byte = 'P'
	for i := 0; i < size; i++ {
		switch {
		case s[i] == 'A':
			if aCnt >= 1 {
				return false
			}
			aCnt += 1
			pre = 'A'
			lCog3 = 0
		case s[i] == 'L':
			if pre == 'L' {
				if lCog3 >= 2 {
					return false
				} else {
					lCog3 += 1
				}
			} else {
				lCog3 += 1
				pre = 'L'
			}
		case s[i] == 'P' && lCog3 > 0:
			lCog3 = 0
		}
	}
	return true
}

/**
 * @Description: 557. Reverse Words in a String III
 * @Keyword: 翻转
 * @Author: kami
 * @Date: 2021/12/27 22:18
 **/
func reverseWords(s string) string {
	sSplit := strings.Split(s, " ")
	var res string
	for i := 0; i < len(sSplit); i++ {
		var temp []byte
		for j := len(sSplit[i]) - 1; j >= 0; j-- {
			temp = append(temp, sSplit[i][j])
		}
		res += " " + string(temp)
	}
	return res[1:]
}

/**
 * @Description: 563. Binary Tree Tilt
 * @Keyword: 先算节点和，再算差值
 * @Author: kami
 * @Date: 2021/12/27 22:24
 **/
func findTilt(root *leetcode.TreeNode) int {
	res := 0
	getSum(root, &res)
	return res
}

func getSum(node *leetcode.TreeNode, tilt *int) int {
	if node == nil {
		return 0
	}

	lsum, rsum := getSum(node.Left, tilt), getSum(node.Right, tilt)
	diff := lsum - rsum
	if diff < 0 {
		diff = -diff
	}
	*tilt += diff

	return lsum + rsum + node.Val
}
